namespace ds
{
    // Character that we will use for trie tree root.
    const HEAD_CHARACTER = '*';

    /**
     * 字典树  (在JavaScript中可由Object对象代替)
     * 
     * 在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。
     * 
     * @see https://github.com/trekhleb/javascript-algorithms/blob/master/src/data-structures/trie/Trie.js
     * @see [Wikipedia](https://en.wikipedia.org/wiki/Trie)
     * @see [YouTube](https://www.youtube.com/watch?v=zIjfhVPRZCg&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=7&t=0s)
     */
    export class Trie
    {
        head: TrieNode;

        constructor()
        {
            this.head = new TrieNode(HEAD_CHARACTER);
        }

        /**
         * @param {string} word
         * @return {Trie}
         */
        addWord(word: string)
        {
            const characters = Array.from(word);
            let currentNode = this.head;

            for (let charIndex = 0; charIndex < characters.length; charIndex += 1)
            {
                const isComplete = charIndex === characters.length - 1;
                currentNode = currentNode.addChild(characters[charIndex], isComplete);
            }

            return this;
        }

        /**
         * @param {string} word
         * @return {Trie}
         */
        deleteWord(word: string)
        {
            const depthFirstDelete = (currentNode, charIndex = 0) =>
            {
                if (charIndex >= word.length)
                {
                    // Return if we're trying to delete the character that is out of word's scope.
                    return;
                }

                const character = word[charIndex];
                const nextNode = currentNode.getChild(character);

                if (nextNode == null)
                {
                    // Return if we're trying to delete a word that has not been added to the Trie.
                    return;
                }

                // Go deeper.
                depthFirstDelete(nextNode, charIndex + 1);

                // Since we're going to delete a word let's un-mark its last character isCompleteWord flag.
                if (charIndex === (word.length - 1))
                {
                    nextNode.isCompleteWord = false;
                }

                // childNode is deleted only if:
                // - childNode has NO children
                // - childNode.isCompleteWord === false
                currentNode.removeChild(character);
            };

            // Start depth-first deletion from the head node.
            depthFirstDelete(this.head);

            return this;
        }

        /**
         * @param {string} word
         * @return {string[]}
         */
        suggestNextCharacters(word: string)
        {
            const lastCharacter = this.getLastCharacterNode(word);

            if (!lastCharacter)
            {
                return null;
            }

            return lastCharacter.suggestChildren();
        }

        /**
         * Check if complete word exists in Trie.
         *
         * @param {string} word
         * @return {boolean}
         */
        doesWordExist(word: string)
        {
            const lastCharacter = this.getLastCharacterNode(word);

            return !!lastCharacter && lastCharacter.isCompleteWord;
        }

        /**
         * @param {string} word
         * @return {TrieNode}
         */
        getLastCharacterNode(word: string)
        {
            const characters = Array.from(word);
            let currentNode = this.head;

            for (let charIndex = 0; charIndex < characters.length; charIndex += 1)
            {
                if (!currentNode.hasChild(characters[charIndex]))
                {
                    return null;
                }

                currentNode = currentNode.getChild(characters[charIndex]);
            }

            return currentNode;
        }
    }

}